﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

using FineCollection.Const;
using FineCollection.Intf;
using FineCollection.Utils;



namespace FineCollection.Cont
{
    /// <summary>
    /// Hash table - a base class for <c>HashSet</c> and <c>HashMap</c>.
    /// </summary>
    /// <typeparam name="T">type of element.</typeparam>
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(HashTableDebugView<>))]
    public class HashTable<T> : WCollection<T>
    {

        /// <summary>
        /// Hash ring module (power).
        /// The hash ring array (<see cref="table"/>) 
        /// should have size exactly as this value.
        /// This value should be prime.
        /// </summary>
        private uint mod; 

        /// <summary>
        /// Table of entries.
        /// Zero based.
        /// </summary>
        private LinkedListImp<T>[] table;

        /// <summary>
        /// Count of actual items.
        /// </summary>
        private int count;


        /// <summary>
        /// Limit of count / mod
        /// </summary>
        internal float CollisionFactorLimit = 3.14f;

        /// <summary>
        /// Multiplier for reorganization.
        /// </summary>
        internal float ReorganizationFactor = 3.14f;

        /// <summary>
        /// Threashold of count.
        /// Reorganization is needed when count has reached this threashold.
        /// Based on mod and collision factor limit.
        /// </summary>
        private int collisionThreashold = 25;


        /// <summary>
        /// Initial mod.
        /// </summary>
        internal const int InitialMod = 37;


        public HashTable()
            : this(0)
        {}


        public HashTable(int capacity)
        {
            mod = capacity > 1 
                ? PrimeNumbers.SelectRingPowerForContainer((uint)capacity) 
                : InitialMod;

            table = new LinkedListImp<T>[mod];
            RecalculateCollisionThreashold();
        }


        private void RecalculateCollisionThreashold()
        {
            collisionThreashold = (int) (mod*CollisionFactorLimit);
        }


        public void Add(T item, int itemHashCode)
        {
            // check for reorganization 
            if (count > collisionThreashold)
                Reorganize();

            // calculate hash index
            uint hIndex = CalcHashIndex(itemHashCode);

            // add the item
            table[hIndex].Add(item, itemHashCode);
            count++;
        }


        private void Reorganize()
        {
            // new hash mod
            uint desiredNumber = (uint) (count*ReorganizationFactor);
            uint newMod = PrimeNumbers.SelectRingPowerForContainer(desiredNumber);
            if (newMod <= mod)
            {
                collisionThreashold *= 2;
                return;
            }

            // save old data
            Chain<T>[] chains = new Chain<T>[count];
            int curChainIndex = 0;
            for (int i = 0; i < mod; i++)
                table[i].ExcludeAll(chains, ref curChainIndex);

            // make new tables
            mod = newMod;
            table = new LinkedListImp<T>[mod];
            RecalculateCollisionThreashold();

            // reorganize
            foreach(Chain<T> chain in chains)
            {
                uint hashIndex = CalcHashIndex(chain.hashCode);
                table[hashIndex].InsertToEnd(chain);
            }
        }


        internal HashChain<T> FindFirst(int hashCode, Predicate<T> predicate)
        {
            uint hashIndex = CalcHashIndex(hashCode);
            return new HashChain<T>
                {
                    hashIndex = hashIndex,
                    chain = table[hashIndex].FindFirst(hashCode, predicate)
                };
        }


        /// <summary>
        /// Checks whether the specified item exists in the table 
        /// (at least one occurence).
        /// </summary>
        /// <typeparam name="TT">type of the item to look for.</typeparam>
        /// <param name="item">item to look for, mandatory for reference types
        ///                    (this function could not search nulls).</param>
        /// <param name="itemHashCode">hash code of the item.</param>
        /// <returns>true if found.</returns>
        public bool Contains<TT>(TT item, int itemHashCode)
            where TT: T, IEquatable<TT>
        {
            bool found;
            CheckExistance(itemHashCode, anItem => anItem.Equals(item), out found);
            return found;
        }


        internal void CheckExistance(int hashCode, Predicate<T> predicate,
                                     out bool found)
        {
            uint hashIndex = CalcHashIndex(hashCode);
            table[hashIndex].CheckExistence(hashCode, predicate, out found);
        }


        internal void Remove(HashChain<T> hchain)
        {
            Debug.Assert(hchain.chain != null);
            table[hchain.hashIndex].Remove(hchain.chain);
            count--;
        }


        internal uint CalcHashIndex(int itemHashCode)
        {
            uint h = (uint)(itemHashCode & 0x7FFFFFFF);
            if (h == 0) h = int.MaxValue;
            return h % mod;
        }


        public void Clear()
        {
            table = new LinkedListImp<T>[mod];
            count = 0;
        }


        /// <summary>
        /// Count of items in the collection.
        /// </summary>
        public int Count
        {
             get { return count; }
        }


        public bool IsEmpty
        {
            get { return count == 0; }
        }

        public bool IsNotEmpty
        {
            get { return count != 0; }
        }


        T RCollection<T>.this[Predicate<T> predicate]
        {
            get { return Find(predicate, default(T)); }
        }


        public T Find(Predicate<T> predicate, T defaultValue)
        {
            if (count > 0)
                for (int i = 0; i < mod; i++)
                    for (var chain = table[i].first; chain != null; chain = chain.next)
                        if (predicate(chain.item))
                            return chain.item;
            return defaultValue;
        }


        public T[] ListAllEntries()
        {
            T[] items = new T[count];
            uint k = 0;
            if (count > 0)
                for (int i = 0; i < mod; i++)
                    // ReSharper disable AccessToModifiedClosure
                    table[i].ProcessAll(item => items[k++] = item);
                    // ReSharper restore AccessToModifiedClosure
            return items;
        }




        #region FULL COLLECTION ITERATORS

        public WIterator<T> TakeIterator()
        {
            return new FullIterator(this);
        }


        RIterator<T> RCollection<T>.TakeIterator()
        {    
            return new FullIterator(this);
        }


        IEnumerator IEnumerable.GetEnumerator()
        {
            return new FullIterator(this);
        }


        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new FullIterator(this);
        }


        internal class FullIterator : WIterator<T>, IEnumerator<T>
        {
            private readonly HashTable<T> htable; 
            private sbyte where;
            private uint index;
            private Chain<T> chain;


            internal FullIterator(HashTable<T> htable)
            {
                this.htable = htable;
                this.where = -1;
            }


            private FullIterator(HashTable<T> htable, sbyte where, uint curIndex, Chain<T> curChain)
            {
                this.chain = curChain;
                this.index = curIndex;
                this.htable = htable;
                this.where = where;
            }


            public void Reset()
            {
                this.where = -1;
                index = 0;
                chain = null;
            }


            public bool Next()
            {
                switch(where)
                {
                case -1:
                    if (htable.IsNotEmpty)
                    {
                        index = 0;
                        while (htable.table[index].count == 0)
                            index++;
                        chain = htable.table[index].first;
                        where = 0;
                    }
                    else
                    {
                        where = +1;
                    }
                    break;
                case 0:
                    if (chain.next != null)
                    {
                        chain = chain.next;
                    }
                    else 
                    {
                        while(true)
                        {
                            index++;
                            if (index >= htable.mod)
                            {
                                where = +1;
                                break;
                            }

                            chain = htable.table[index].first;
                            if (chain != null)
                            {
                                break;
                            }
                        }
                    }
                    break;
                }

                return where == 0;
            }


            public T Current
            {
                get
                {
                    if (where == 0)
                    {
                        return chain.item;
                    }
                    else
                    {
                        throw new OutOfCollectionException("Attempting to get value from an iterator when teh iterator state is before/after the collection.");
                    }
                }
            }


            public sbyte Where
            {
                get { return where; }
            }


            RIterator<T> RIterator<T>.Clone()
            {
                return new FullIterator(htable, where, index, chain);
            }


            public WIterator<T> Clone()
            {
                return new FullIterator(htable, where, index, chain);
            }


            //RIterator<T> RIterator<T>.Clone()
            //{
            //    return new FullIterator(htable, where, index, chain);
            //}


            object IEnumerator.Current
            {
                get { return Current; }
            }


            public T Exclude()
            {
                if (where != 0)
                    throw new OutOfCollectionException(
                        "Attempting to exclude item from an iterator when the iterator state is before/after the collection.");
                
                var excluding = chain;
                var excludingHC = 
                    new HashChain<T> {chain = excluding, hashIndex = index };
                Next();
                htable.Remove(excludingHC);

                return excluding.item;
            }

                                                      
            bool IEnumerator.MoveNext()
            {
                if (where < +1)
                    return Next(); // shifts the iterator
                else
                    return false;
            }


            public void Dispose()
            {
                chain = null;
                where = +1;
            }
        }

        #endregion



    }



    /// <summary>
    /// Hash table cell link.
    /// </summary>
    /// <typeparam name="T">type of table item.</typeparam>
    internal struct HashChain<T>
    {
        /// <summary>
        /// Index of a backet.
        /// </summary>
        internal uint hashIndex;

        /// <summary>
        /// Chain in the backet, or null if not found.
        /// </summary>
        internal Chain<T> chain;

        /// <summary>
        /// Chain in the backet, or null if not found.
        /// </summary>
        public Chain<T> Chain { get { return chain; } }
    }



    #region DEBUG HELPER

    /// <summary>
    /// Debug helper.
    /// </summary>
    internal class HashTableDebugView<T>
    {
        private readonly HashTable<T> table;


        public HashTableDebugView(HashTable<T> table)
        {
            this.table = table;
        }


        [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
        public Array Items
        {
            get
            {
                return table != null 
                    ? DebugViewUtils.MakeArray(table.ListAllEntries(), 1, table.Count) 
                    : new T[0];
            }
        }
    }

    #endregion


}
